import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Solution480 {

    public void sortArr(List<Integer> eleList){
        Collections.sort(eleList);
    }

    public double getMid(List<Integer> eleList){
        if(eleList.size()%2==1){
            return (double)eleList.get(eleList.size()/2);
        }
        double sum=0;
        sum+=eleList.get(eleList.size()/2);
        sum+=eleList.get((eleList.size()/2)-1);
        return sum/2;
    }

    public void insert(List<Integer> eleList,Integer target){
        eleList.add(binarySearch(eleList,target),target);
    }



    public int binarySearch(List<Integer> eleList,int target){
        int lo=0;
        int hi=eleList.size()-1;
        int mid;
        while(lo<=hi){
            mid=(lo+hi)/2;
            if(eleList.get(mid)==target){
                return mid;
            }else if(eleList.get(mid)<target){
                lo=mid+1;
            }else{
                hi=mid-1;
            }
        }
        return lo;
    }

    public double[] medianSlidingWindow(int[] nums, int k) {
        double[] result=new double[nums.length-k+1];
        List<Integer> eleList=new LinkedList<>();
        for (int i = 0; i < k; i++) {
            eleList.add(nums[i]);
        }
        sortArr(eleList);
        result[0]=getMid(eleList);
        int tmpIndex=1;
        for (int i = k; i < nums.length; i++) {
            //insert(eleList,nums[i]);
            eleList.add(nums[i]);
            sortArr(eleList);
            eleList.remove((Object)nums[i-k]);
            result[tmpIndex]=getMid(eleList);
            tmpIndex++;
        }
        return result;
    }

    public static void main(String[] args) {
        Solution480 s=new Solution480();
        System.out.println(s.medianSlidingWindow(new int[]{-2147483648,-2147483648,2147483647,-2147483648,-2147483648,-2147483648,2147483647,2147483647,2147483647,2147483647,-2147483648,2147483647,-2147483648},
        3));
    }
}
